package listbyorder.access1001a.test1289;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/8/20 17:26
 */
public class Solution2 {

    int res = Integer.MAX_VALUE;

    public int minFallingPathSum(int[][] arr) {
        if(arr == null || arr.length == 0 || arr[0].length == 0) return 0;
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            dfs(arr, 0, i, 0, n);
        }
        return res;
    }

    private void dfs(int[][] arr, int i, int j, int sum, int n) {
        if(j == 0 || j == n || sum > res) return;
        if(i == n) {
            res = Math.min(res, sum);
            return;
        }
        sum += arr[i][j];
        dfs(arr, i + 1, j - 1, sum, n);
        dfs(arr, i + 1, j + 1, sum, n);
    }
}
